
**关于优化问题**  
计算机科学中许多算法都是为了找到某些问题的最优解。 (例：地图上两个点之间的最短路径，能最好匹配一系列点的直线; 或者满足一定条件的最小集合。)

### 找零兑换问题  
一个经典案例是兑换最少个数的硬币问题 假设你为一家自动售货机厂家编程序，自动售货 机要每次找给顾客最少数量硬币;  
假设某次顾客投进$1纸币，买了ȼ37美分的东西，要找ȼ63美分，那么最少数量就是:2个quarter(ȼ25) 、1个dime(ȼ10)和3个penny(ȼ1)，一共6个。

- 解决思路  
    我们使用贪心策略来解决这个问题。从最大面值的硬币开始，用尽量多的数量，有余额的，再到下一最大面值的硬币，还用尽量 多的数量，一直到penny(ȼ1)为止。  
    答案：ȼ63 = ȼ25x2 + ȼ10x1 + ȼ1x3

### 找零兑换碰到了问题  
除了上面3种面值之外，又新增了一种【ȼ21】的硬币。

- 理想状态：ȼ63 = ȼ21x3  
- 贪心策略：ȼ63 = ȼ25x2 + ȼ10x1 + ȼ1x3 
- `贪心策略”失效了`


### 递归解法

:::tip 
思路：  
首先是确定基本结束条件，兑换硬币这个问题最简单直接的情况就是，需要兑换的找零，其面值正好等于某种硬币 如找零25分，答案就是1个硬币!   
其次是减小问题的规模，我们要对每种硬币尝试1次，例如美元硬币体系:  
找零减去1分(penny)后，求兑换硬币最少数量(递归调用 自身);  
找零减去5分(nikel)后，求兑换硬币最少数量;   
找零减去10分(dime)后，求兑换硬币最少数量;   
找零减去25分(quarter)后，求兑换硬币最少数量 上述4项中选择最小的一个。  
:::

- python
```python
def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList: # 其面值正好等于面值列表里，直接返回1
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]: # 生成一个 <= chang的列表并循环
            numCoins = 1 + recMC(coinValueList, change-i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins
print(recMC([1,5,10,25], 63))
```
:::info
极!其!低!效!  
对63分的兑换硬币问题，需要进行67,716,925 次递归调用!  
在我这台笔记本电脑上花费了40秒时间得到解: 6个硬币  
这个算法致命缺点是重复计算。
::: 

#### 改进递归算法
- 对这个递归解法进行改进的关键就在于消除重复计算，我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过。
这个算法的中间结果就是部分找零的最优解，在递归调用过程中已经得到的最优解被记录下来,在递归调用之前，先查找表中是否已有部分找零的最优解。
如果有，直接返回最优解而不进行递归调用如果没有，才进行递归调用。

- python
```python
def recMC(coinValueList, change,knownResults):
    minCoins = change
    if change in coinValueList: # 递归基本结束条件
        return 1 ## 记录最优解
    elif knownResults[change] > 0:
        return knownResults[change] # 查表成功，直接用最优解
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins # 找到最优解，记录到表中
    return minCoins
print(recMC([1,5,10,25], 63, [0]*64))
```

:::info
改进后的解法，极大减少了递归调用次数 对63分兑换硬币问题，仅仅需要221次递归调用是改进前的三十万分之一，瞬间返回!
:::